package com.acwing.partition6;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/20 9:11
 */
public class AC524愤怒的小鸟 {

    private static final double EPS = 1e-6;
    private static final int INF = 0x3f3f3f3f;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int t = Integer.parseInt(s[0]);
        for (int i = 0; i < t; i++) {
            s = reader.readLine().split("\\s+");
            int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
            double[][] points = new double[n][2];
            for (int j = 0; j < n; j++) {
                s = reader.readLine().split("\\s+");
                points[j][0] = Double.parseDouble(s[0]);
                points[j][1] = Double.parseDouble(s[1]);
            }
            writer.write(dynamicProgramming(points) + "\n");
        }
        writer.flush();
    }

    private static int dynamicProgramming(double[][] points) {
        int n = points.length;
        //states[i][j]表示i点和j点所确定的抛物线能覆盖的点的状态
        int[][] states = new int[n][n];
        //每两个点确定一条抛物线，并枚举计算出来的抛物线能覆盖哪些点，将覆盖状态保存在states中
        for (int i = 0; i < n; i++) {
            double x1 = points[i][0], y1 = points[i][1];
            //单独生成一条只经过(0,0)和(x,y)的抛物线
            states[i][i] = 1 << i;
            for (int j = 0; j < n; j++) {
                double x2 = points[j][0], y2 = points[j][1];
                if (compareDouble(x1, x2) == 0) continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2), b = y1 / x1 - a * x1;
                if (compareDouble(a, 0.0) >= 0) continue;
                //枚举这条抛物线能覆盖的点，并将能经过的点的状态保存下来
                int state = 0;
                for (int k = 0; k < n; k++) {
                    double x = points[k][0], y = points[k][1];
                    if (compareDouble(a * x * x + b * x, y) == 0) state |= 1 << k;
                }
                states[i][j] = state;
            }
        }
        //dp[i]表示覆盖状态i的点至少需要的抛物线数量
        int[] dp = new int[1 << n];
        for (int i = 1; i < 1 << n; i++) dp[i] = INF;
        for (int curr = 0; curr < 1 << n - 1; curr++) {
            int x = -1;
            //找到当前状态中没有被覆盖的点，表示需要一条新的抛物线来覆盖
            for (int j = 0; j < n; j++) {
                if ((curr >> j & 1) == 0) {
                    x = j;
                    break;
                }
            }
            if (x == -1) continue;
            for (int y = 0; y < n; y++) {
                int next = curr | states[x][y];
                dp[next] = Math.min(dp[curr] + 1, dp[next]);
            }
        }
        return dp[(1 << n) - 1];
    }

    private static int compareDouble(double a, double b) {
        if (Math.abs(a - b) < EPS) return 0;
        return a < b ? -1 : 1;
    }
}
